from copy import deepcopy

import random
from tqdm import tqdm

# 道路数量
road_num=63968
# 路口数量
cross_num=8000
# 游戏总时长
max_time=858
# 车辆总数
car_num=200
# 按时到达时的基础得分
base_score=250

def error(s):
    print("\033[31m",s,"\033[0m")

class Roads:
    def __init__(self,game,need_check=True):
        print("------------- begin road init ------------------")
        self.pass_cross=[]
        self.last_pass_cross=[1 for i in range(cross_num)]
        self.game=game
        self.Waitting=[[[] for i in range(cross_num)]for j in range(cross_num)]
        self.green=[[0 for i in range(cross_num)]for j in range(cross_num)]
        self.red=[[0 for i in range(cross_num)]for j in range(cross_num)]
        # 第一次绿灯开始时间
        self.green_first=[[0 for i in range(cross_num)]for j in range(cross_num)]
        self.need_check=need_check
        self.all_road=[]
        # 算法优先级，1为最大优先级，数越大优先级越小，优先级高的算法可以改优先级低的算法的设置值
        self.priority=[[-1 for i in range(cross_num)]for j in range(cross_num)]
        print("-------------- end road init -------------------")

    # 根据优先级更新数据，优先级高的可以修改优先级低的数据
    def update_green(self,x,y,value,priority):
        if self.priority[x][y]!=-1 and priority>self.priority[x][y]:
            error('not update_green x:'+str(x)+',y:'+str(y)+',value:'+str(value)+',priority:'+str(priority)+'self.priority:'+str(self.priority[x][y]))
            return
        self.priority[x][y]=priority
        self.green[x][y]=value


    def road_append(self,road):
        self.all_road.append(road)

    # 检测红绿灯是否设置合理，在同一个路口内，同一时间只能有一个路口亮绿灯
    def check_right(self):
        if  not self.need_check:
            return True

        for i in range(cross_num):
            vis=[0 for i in range(max_time)]
            begin_cross=[]
            all_green_time=0
            for j in range(cross_num):
                for g in range(self.green[j][i]):

                    if g+self.green_first[j][i]>=max_time:
                        continue
                    if vis[g+self.green_first[j][i]]==1:
                        error('1首次出现绿灯的时间错误' + '错误路口有:' + str(i)+',g:'+str(g)+',j:'+str(j)+',i:'+str(i)+',self.green_first:'+str(self.green_first[j][i])+',self.green'+str(self.green[j][i])+'priority:'+str(self.priority[j][i]))
                        for ej in range(cross_num):
                            if self.green[ej][i]>0:
                                print('ej:',ej,'i:',i,'self.green',self.green[ej][i],'green_first:',self.green_first[ej][i])
                        return False
                    vis[g + self.green_first[j][i]] = 1
                if self.game.street[j][i]!=-1 and self.green[j][i]!=0:
                    begin_cross.append(j)
                    all_green_time+=self.green[j][i]
            for j in begin_cross:
                if self.red[j][i]!=all_green_time-self.green[j][i]:
                    error('道路红绿灯时间错误:'+'路口为:'+str(i))
                    return False
                if self.green_first[j][i]>all_green_time-self.green[j][i]+1:
                    error('--------------error-------------------')
                    print('begin_cross:',begin_cross)
                    for b in begin_cross:
                        print('begin:',b,'end:',i,'self.green_first:',self.green_first[b][i],'green_time:',self.green[b][i])
                    error('2首次出现绿灯的时间错误' + '错误路口有:' + str(i)+',j:'+str(j)+',self.green_first:'+str(self.green_first[j][i])+',all_green_time:'+str(all_green_time)+',green_time:'+str(self.green[j][i]))
                    return False
        return True

    # 根据绿灯的值设定红灯
    def update_red(self):
        for i in range(cross_num):
            begin_cross=[]
            all_green_time=0
            for j in range(cross_num):
                if self.game.street[j][i] != -1:
                    if self.green[j][i]!=0:
                        begin_cross.append(j)
                        all_green_time += self.green[j][i]
                    else:
                        self.red[j][i]=max_time
            for j in begin_cross:
                self.red[j][i] = all_green_time - self.green[j][i]

    def move_next(self,time):
        for i in range(road_num):
            x=self.all_road[i].begin
            y=self.all_road[i].end
            num=len(self.Waitting[x][y])
            w = self.Waitting[x][y]
            if num>0:
                if y in self.pass_cross:
                    now_g = time - self.last_pass_cross[y]+1
                    if now_g<=0:
                        continue
                    flag = self.game.car[w[0] - 1].move_next_road(time)
                    if flag:
                        w.remove(w[0])

                        self.update_green(x,y,now_g,3)
                        self.green_first[x][y]=self.last_pass_cross[y]
                        self.last_pass_cross[y]=time+1
                        # print("set road op 3 by,x:",x,'y:',y,'now_g:',now_g,',priority',self.priority[x][y],'self.green_first:',self.green_first[x][y],'time:',time)
                    continue
                r=self.green[x][y]+self.red[x][y]
                temp_time=time-self.green_first[x][y]+1
                if temp_time<0:
                    continue
                left=temp_time%r
                if left==0:
                    left=r

                if left<=self.green[x][y]:
                    flag=self.game.car[w[0]-1].move_next_road(time)
                    if flag:
                        w.remove(w[0])


class Road:
    def __init__(self):
        self.begin = 0
        self.end = 0


    def set_begin_and_end(self,begin,end):
        self.begin = begin
        self.end = end


    # 进行路径解析，将字母的路径转化成数字路径
    def road_decode(self,path):
        s_p=path.split('-')
        if(len(s_p)!=2):
            print(path," is not right path")
            exit(-1)
        self.begin=self.str_to_int(s_p[0])
        self.end=self.str_to_int(s_p[1])

    def str_to_int(self,s):
        sum=0
        for i in range(len(s)):
            if ord(s[i])>=ord('a') and ord(s[i])<=ord('z'):
                sum *= 10
                sum+=int(ord(s[i])-ord('a'))
            else:
                break
        return sum

    def show(self,end='\n'):
        print(self.begin,'->',self.end,end=end)

class Car:
    def __init__(self,index,game):
        self.game=game
        self.car_index=index

        self.position=-1
        self.current_road_left=-1
        self.last_move_time=0
        self.arrived=False

    def reset(self):
        self.position=0
        self.current_road_left=0
        self.last_move_time=0
        self.arrived=False

    def RoadInit(self,path_len,path):

        self.road=[]
        for i in range(path_len):
            temp = Road()
            temp.road_decode(path[i])
            self.road.append(temp)
        if path_len < 0:
            return
        self.position=0
        self.current_road_left=0

    def show(self):
        print("car_index:",self.car_index,"position:",self.position,"current_road_left:",self.current_road_left,'path_len:',len(self.road))
        for i in self.road:
            i.show(end=' ')
        print()

    def is_arrived(self):
        return self.arrived

    # 更新车辆移动一步之后的状态
    def  move_next(self,time):
        if self.is_arrived():
            return
        if self.last_move_time>=time:
            return
        if time==1:
            self.game.roads.Waitting[self.road[self.position].begin][self.road[self.position].end].append(
                self.car_index)
            if self.road[self.position].end in self.game.car_bigger_road:
                if self.road[self.position].begin not in self.game.car_bigger_road_vis[self.road[self.position].end]:
                    self.game.car_bigger_road_vis[self.road[self.position].end].append(self.road[self.position].begin)

        if self.current_road_left<=0:
            return
        self.current_road_left-=1
        self.last_move_time=time

        if self.current_road_left==0:
            if self.position<len(self.road)-1:
                # 记录一些节点，第一次有车到达的路是哪些
                if self.road[self.position].end in self.game.car_bigger_road:
                    if self.road[self.position].begin not in self.game.car_bigger_road_vis[self.road[self.position].end]:
                        self.game.car_bigger_road_vis[self.road[self.position].end].append(self.road[self.position].begin)


                self.game.roads.Waitting[self.road[self.position].begin][self.road[self.position].end].append(self.car_index)
            else:
                self.arrived=True

    # 将车移动到下一个道路上
    def move_next_road(self,time):
        if self.last_move_time>=time:
            return False
        self.last_move_time = time

        self.position+=1
        x=self.road[self.position].begin
        y=self.road[self.position].end
        self.current_road_left=self.game.street[x][y]


        return True





class Game:
    def __init__(self):
        self.current_time=0
        self.roads = Roads(self)
        self.street=[[-1 for i in range(8000)] for j in range(8000)]
        self.streetInit()
        self.car=[Car(i+1,self) for i in range(200)]
        self.carInit()
        self.car_bigger_road=[]
        self.car_bigger_road_all={}
        self.car_bigger_road_vis={}

    # 重置游戏状态，如车辆状态，和等待状态
    def reset_game(self):
        for i in range(car_num):
            self.car[i].reset()
        for i in range(cross_num):
            for j in range(cross_num):
                self.roads.Waitting[i][j]=[]
        for i in range(cross_num):
            self.roads.last_pass_cross[i]=1
        for i in self.car_bigger_road:
            self.car_bigger_road_vis[i]=[]
        for i in self.roads.pass_cross:
            for j in range(cross_num):
                if self.roads.priority[j][i]==3:
                    self.roads.green_first[j][i]=0
                    self.roads.green[j][i]=0




    # 初始化街道数据
    def streetInit(self):
        print("------------ begin street init -----------------")
        index = -1
        with open("streets.txt",'r') as f:
            for js in f.readlines():
                index += 1
                if index==0:
                    continue
                s=js.split(',')
                x=int(s[1])
                y=int(s[2])
                temp=Road()
                temp.set_begin_and_end(x,y)
                self.roads.road_append(temp)
                len=int(s[3])
                self.street[x][y]=len

    # 初始化车辆的数据
    def carInit(self):
        print("-------------- begin car init ------------------")
        with open("cars.txt",'r') as f:
            index=0
            for js in f.readlines():
                s = js.split(',')
                path_len=int(s[1])
                path=[s[2+i] for i in range(path_len)]
                self.car[index].RoadInit(path_len,path)
                index += 1

    def show_all_car(self):
        for car in self.car:
            car.show()

    # 游戏进程
    def run(self):
        self.roads.update_red()
        print("---------------- begin game---------------------")
        for time in tqdm(range(1,max_time+1)):
            for i in range(car_num):
                self.car[i].move_next(time)
            self.roads.move_next(time)


    # 优化一，将所有未经过的路径的红绿灯都设置为红灯，并且首次绿灯时间等于max_time
    def optimization_untouch_road(self,priority=1):
        vis=[[0 for i in range(cross_num)]for j in range(cross_num)]

        for i in range(car_num):
            for j in range(len(self.car[i].road)):
                if j==len(self.car[i].road)-1:
                    continue
                r=self.car[i].road[j]
                vis[r.begin][r.end]+=1
        counts=0
        for r in self.roads.all_road:
            if vis[r.begin][r.end]==0:
                self.roads.update_green(r.begin,r.end,0,priority)

                counts+=1
        print("after optimization_untouch_road we can move",counts,'path')

    # 优化二，路口只有一条路的情况，这条路全绿灯
    def optimization_touch_road_ones(self, priority=2):
        vis_end=[0 for i in range(cross_num)]
        vis_begin=[0 for i in range(cross_num)]
        for i in range(cross_num):
            for j in range(cross_num):
                if self.street[j][i] !=-1 and (self.roads.priority[j][i]==-1 or self.roads.priority[j][i]>priority):
                    vis_end[i] += 1
                    vis_begin[i]=j
        counts = 0
        for i in range(cross_num):
            if vis_end[i]==1:

                x=vis_begin[i]
                y=i
                if self.roads.priority[x][y]==-1 or self.roads.priority[x][y]>priority:
                    counts += 1
                    self.roads.update_green(x,y,max_time,priority)
                    self.roads.green_first[x][y]=1
                    #print('op1,i:',i,'vis_end:',vis_end[i])
            # elif vis_end[i]>1:
            #     print("排序数列:",i,'->',vis_end[i])

        print("after optimization_touch_road_ones we can move",counts,'path')

    # 优化三，当终点道路为n，且经过道路的车辆为n，就是每一条道路只经过一辆车时可以完成优化
    def optimization_one_road_one_car(self):
        vis_road=[0 for i in range(cross_num)]
        vis_car=[0 for i in range(cross_num)]
        for i in range(cross_num):
            num = 0
            for j in range(cross_num):
                if self.street[j][i] != -1 and self.roads.priority[j][i] == -1:
                    vis_road[i] += 1
        for i in range(car_num):
            for j in range(len(self.car[i].road)):
                if j==len(self.car[i].road)-1:
                    continue
                r=self.car[i].road[j]
                if self.street[r.begin][r.end] != -1 and self.roads.priority[r.begin][r.end] == -1:
                    vis_car[r.end] += 1
        count=0
        count_road=0
        self.roads.pass_cross=[]
        for i in range(cross_num):
            if vis_road[i]>1 and vis_road[i]==vis_car[i]:
                count+=1
                count_road+=vis_road[i]
                #print('pass_cross.append,i:',i,',vis_road:',vis_road[i],'vis_car:',vis_car[i])
                self.roads.pass_cross.append(i)
            elif vis_road[i]>0:
                self.car_bigger_road.append(i)
                self.car_bigger_road_all[i]=[]
                self.car_bigger_road_vis[i]=[]
                print("road", i, 'same in road:', vis_road[i], 'car:', vis_car[i])
        for i in range(cross_num):
            if i in self.car_bigger_road:
                for j in range(cross_num):
                    if self.street[j][i] != -1 and self.roads.priority[j][i] == -1:
                        self.car_bigger_road_all[i].append(j)

        print("pass_cross:",self.roads.pass_cross)
        print("after optimization_one_road_one_car we can move",count,'node')
        print("after optimization_one_road_one_car we can move",count_road, 'path')




    def count_every_node_road_num(self):
        for i in range(cross_num):
            num=0
            for j in range(cross_num):
                if self.street[j][i]!=-1 and self.roads.priority[j][i]==-1:
                    num+=1
            if num>1:
                print("node:",i,'left ',num,'road')

    # 计算总得分
    def countSocre(self,out=True):
        sum=0
        for i in range(car_num):
            if self.car[i].is_arrived():
                sum+=base_score+(max_time-self.car[i].last_move_time)
                if out:
                    print("car:",self.car[i].car_index,'get score',base_score+(max_time-self.car[i].last_move_time))
        return sum

    # 实现粒子群算法
    def particle_solve(self,turn=30,priority=4):
        particle_num = 12
        c1=2
        c2=2
        g_best=0
        y=[0 for i in range(particle_num)]
        b_best=[0 for i in range(particle_num)]
        g_best_x=[]
        b_best_x=[[] for i in range(particle_num)]
        all_road=[]
        road_index={}
        green_first=[[] for i in range(particle_num)]
        x=[[] for i in range(particle_num)]
        v=[[] for i in range(particle_num)]
        all_road_num={}
        for p_index in range(particle_num):
            index=0
            first_time=1
            for i in self.car_bigger_road:
                left_time=max_time
                all_road_num[i]=len(self.car_bigger_road_all[i])
                road_num=len(self.car_bigger_road_all[i])-1
                for j in self.car_bigger_road_vis[i]:
                    if p_index==0:
                        all_road.append((j,i))
                    if j not in road_index:
                        road_index[j]={}
                    road_index[j][i] = index
                    # r=random.randint(1, left_time-road_num)
                    r = random.randint(1, 20)
                    left_time-=r
                    road_num-=1
                    x[p_index].append(r)
                    v[p_index].append(random.random()*4)
                    green_first[p_index].append(first_time)
                    first_time+=r
                    index+=1
                for j in self.car_bigger_road_all[i]:
                    if j in self.car_bigger_road_vis[i]:
                        continue
                    if p_index==0:
                        all_road.append((j,i))
                    if j not in road_index:
                        road_index[j]={}
                    road_index[j][i] = index
                    # r=random.randint(1, left_time-road_num)
                    r = random.randint(1, 20)
                    left_time-=r
                    road_num-=1
                    x[p_index].append(r)
                    v[p_index].append(random.random()*4)
                    green_first[p_index].append(first_time)
                    first_time+=r
                    index+=1
        print("x_len:",len(x[0]))
        print('all_road:',all_road)
        for i in range(turn):
            w=0.4

            for j in range(particle_num):
                self.reset_game()
                #更新参数
                if i!=0:
                    x_len = len(x[j])
                    temp_time = [max_time for i in range(cross_num)]
                    temp_all_road_num = deepcopy(all_road_num)
                    for k in range(x_len):
                        v[j][k] = w * v[j][k] + c1 * random.random() * (b_best_x[j][k] - x[j][k]) + c2 * random.random() * (
                                    g_best_x[k] - x[j][k])
                        x[j][k] += v[j][k]
                        x[j][k] = round(x[j][k])
                        if x[j][k] < 1:
                            x[j][k] = 1
                        elif x[j][k] > temp_time[all_road[k][1]] - temp_all_road_num[all_road[k][1]] + 1:
                            x[j][k] = temp_time[all_road[k][1]] - temp_all_road_num[all_road[k][1]] + 1
                        temp_time[all_road[k][1]] -= x[j][k]
                        temp_all_road_num[all_road[k][1]] -= 1

                # 根据道路的车辆第一次到达路口的时间来更新红绿灯的顺序
                for e in self.car_bigger_road:
                    first_time = 1
                    for b in self.car_bigger_road_vis[e]:
                        green_first[j][road_index[b][e]] = first_time
                        first_time += x[j][road_index[b][e]]
                    for b in self.car_bigger_road_all[e]:
                        if b in self.car_bigger_road_vis[e]:
                            continue
                        green_first[j][road_index[b][e]] = first_time
                        first_time += x[j][road_index[b][e]]

                for k in range(len(all_road)):
                    begin=all_road[k][0]
                    end=all_road[k][1]
                    if self.roads.priority[begin][end]==-1 or self.roads.priority[begin][end]>=priority:
                        self.roads.update_green(begin,end,x[j][k],priority)
                        self.roads.green_first[begin][end]=green_first[j][k]
                self.roads.update_red()
                print('turn:',i,'particle_index:',j)
                flag=self.roads.check_right()
                print(flag)
                if not flag:
                    error("turn:"+str(i)+' j:'+str(j)+' check_right:'+str(flag))
                    exit(-1)

                print(x[j])
                self.run()
                y[j]=self.countSocre(out=False)
                if b_best[j]<y[j]:
                    b_best[j]=y[j]
                    b_best_x[j]=deepcopy(x[j])
                    if g_best<b_best[j]:
                        g_best=b_best[j]
                        g_best_x=deepcopy(x[j])

                game.save_result('./result/turn_'+str(i)+'_p_'+str(j)+'_y_'+str(y[j])+'_g_best_'+str(g_best)+'.txt')
                print("g_best:",g_best)
                # 更新参数
                if i==-1:
                    x_len=len(x[j])
                    temp_time=[max_time for i in range(x_len)]
                    temp_all_road_num=deepcopy(all_road_num)
                    for k in range(x_len):
                        v[j][k]=w*v[j][k]+c1*random.random()*(b_best[j]-x[j][k])+c2*random.random()*(g_best-x[j][k])
                        x[j][k]+=v[j][k]
                        x[j][k]=round(x[j][k])
                        if x[j][k]<1:
                            x[j][k]=1
                        elif x[j][k]>temp_time[k]-temp_all_road_num[all_road[k][1]]+1:
                            x[j][k]=temp_time[k]-temp_all_road_num[all_road[k][1]]+1
                        temp_time[k]-=x[j][k]
                        temp_all_road_num[all_road[k][1]]-=1

                    # 根据道路的车辆第一次到达路口的时间来更新红绿灯的顺序
                    for e in self.car_bigger_road:
                        first_time=1
                        for b in self.car_bigger_road_vis[e]:
                            green_first[j][road_index[b][e]]=first_time
                            first_time+=x[j][road_index[b][e]]
                        for b in self.car_bigger_road_all[e]:
                            if b in self.car_bigger_road_vis[e]:
                                continue
                            green_first[j][road_index[b][e]] = first_time
                            first_time += x[j][road_index[b][e]]


    def save_result(self,name='result.txt'):
        node_sum=0
        result=[]
        for i in range(cross_num):
            c_n=0
            t=[-1 for i in range(max_time+1)]
            for j in range(cross_num):
                if self.roads.green[j][i]!=0:
                    c_n+=1
                    t[self.roads.green_first[j][i]]=(self.roads.green[j][i],j)
            if c_n>0:
                node=[]
                node.append(i)
                node.append(c_n)
                node.append(t)
                node_sum+=1
                result.append(node)

        with open(name,'w') as f:
            f.write(str(node_sum)+'\n')
            for i in range(node_sum):
                f.write(str(result[i][0]))
                f.write('\n')
                f.write(str(result[i][1]))
                f.write('\n')
                for j in result[i][2]:
                    if j==-1:
                        continue
                    f.write(int_to_str(j[1])+'-'+int_to_str(i)+','+str(j[0]))
                    f.write('\n')





def int_to_str(i):
    x=[]
    if i==0:
        x.append('a')
    while i>0:
        k=i%10
        i//=10
        x.append(chr(int(k)+ord('a')))
    s=''
    for i in x:
        s=s+i

    s=''.join(reversed(s))
    return s




if __name__=='__main__':
    game=Game()
    game.optimization_untouch_road()
    game.optimization_touch_road_ones()
    game.optimization_one_road_one_car()

    game.roads.update_red()
    game.save_result('./result/test.txt')
    game.run()

    game.roads.update_red()
    print(game.roads.check_right())
    print(game.countSocre())
    game.particle_solve()

